package cn.edu.xjtu.work.plusOne;

import java.util.Arrays;

/**
 * 加一
 * 
 * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位，
 * 数组中每个元素只存储单个数字。你可以假设除了整数0之外，这个整数不会以零开头。
 */
public class Solution {
  public static void main(String[] args) {
    int[] digits = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    System.out.println(Arrays.toString(plusOne(digits)));
  }

  public static int[] plusOne(int[] digits) {
    if (digits[0] == 0) {
      return new int[] { 1 };
    }
    // 判断是否全为9,即是否需要扩大数组
    boolean firstCarry = true;
    for (int i : digits) {
      if (i != 9) {
        firstCarry = false;
      }
    }

    // 如果需要首位进位那么数组长度需要加一
    int len = firstCarry ? digits.length + 1 : digits.length;
    int[] ret = new int[len];
    if (firstCarry) {
      ret[0] = 1;
    }

    // 在这进行循环, 依次判断每位是否都需要进位
    int carry = 1;// 默认设置carry为1,即最低为需要加一
    for (int i = digits.length - 1; i >= 0; i--) {
      len--;
      if (digits[i] == 9 && carry == 1) {
        ret[len] = 0;
        carry = 1;
      } else {
        ret[len] = digits[i] + carry;
        carry = 0;
      }
    }
    return ret;
  }
}
